#__author__=='qustl_000'
#-*- coding: utf-8 -*-
from numpy import *

'''输出排序结果函数'''
def Print(ddata):
    n=len(ddata)
    for i in range(n):
        print ddata[i],    #其中"，"为了不让其输出默认的换行符
'''插入排序---直接插入排序'''
def ZhiJieChaRuPaiXu(data):
    n=len(data)
    for i in range(1,n):
        if(data[i]<data[i-1]):
            ShaoBing=data[i]
            j=i-1
            while(ShaoBing<data[j]):      #每次移动一个数据
                data[j+1]=data[j]
                j=j-1
                if(j==-1):                #当j为-1时，表明ShaoBing为最小元素，
                    data[0]=ShaoBing
                    break
            data[j+1]=ShaoBing
    Print(data)
'''插入排序---希尔排序'''
def ShellInsertSort(data,dk,n):
    for i in range(dk,n):
        if(data[i-dk]>data[i]):
            j=i-dk
            ShaoBing=data[i]
            while(ShaoBing<data[j]):
                data[j+dk]=data[j]
                if(j<0 and (data[j]==data[j+dk])):  #由于Python列表有负索引，此处为了避免索引值
                    break
                j-=dk
            data[j+dk]=ShaoBing
    return data
def ShellSort(data):
    n=len(data)
    dk=n/2
    while(dk>=1):
        ShellInsertSort(data,dk,n)
        dk=dk/2
    Print(data)
'''简单选择排序'''
def findMin(data):           #寻找最小值和其索引
    global k
    n=len(data)
    minData=data[0]
    for i in range(n):
        if(data[i]<=minData):
            minData=data[i]
            k=i
    return minData,k
def simSelectSort(data):
    n=len(data)
    b=[]
    for i in range(n):
        minData,minIndex=findMin(data)
        b.append(data[minIndex])
        data[minIndex]=inf
    Print(b)
'''二元选择排序'''
def findMax(data):
    n=len(data)
    maxData=data[0]
    maxIndex=0
    for i in range(n):
        if maxData<=data[i]:
            maxData=data[i]
            maxIndex=i
    return maxData,maxIndex
def ErYuanSelectSort(data):
    n=len(data)
    for i in range(n/2):
        minIndex=i;maxIndex=n-i-1
        if(data[minIndex]>data[maxIndex]):
            data[minIndex],data[maxIndex]=data[maxIndex],data[minIndex]
        for j in range(i,n-i):
            if data[minIndex]>=data[j]:
                minIndex=j
            if data[maxIndex]<=data[j]:
                maxIndex=j
        data[i],data[minIndex]=data[minIndex],data[i]
        data[n-i-1],data[maxIndex]=data[maxIndex],data[n-i-1]
        print ' '
    Print(data)
'''堆排序'''
def heapAdjust(data,s,n):        #堆调整函数，data---数据，s---为待调整节点位置，n---数据长度
    child=2*s+1
    while(child<n):
        if(child+1<n and data[child]<data[child+1]):
            child+=1
        if(data[s]<data[child]):
            data[s],data[child]=data[child],data[s]
            s=child
            child=2*s+1
        else:
            break
    return data
def buildHeap(data,n):                 #建立初始堆
    for i in range(-1,(n-1)/2)[::-1]:  #[::-1]实现倒序循环
        data=heapAdjust(data,i,n)
    return data
def heapSort(data,n):
    data=buildHeap(data,n)
    for i in range(n-1)[::-1]:
        data[0],data[i]=data[i],data[0]
        data=heapAdjust(data,0,i)
    Print(data)
'''冒泡排序'''
def bubbleSort(data,n):
    for i in range(n)[::-1]:
        for j in range(1,n-1):
            if data[j]<data[j-1]:
                data[j],data[j-1]=data[j-1],data[j]
    Print(data)
'''冒泡排序优化方法1---加入变化标志'''
def bubbleSortOpt1(data,n):
    for i in range(n)[::-1]:
        change=0
        for j in range(1,n):
            if data[j]<data[j-1]:
                change+=1
                data[j],data[j-1]=data[j-1],data[j]
        if change==0:
            break
    Print(data)
'''冒泡排序优化方法2---记录变化位置'''
def bubbleSortOpt2(data,n):
    for i in range(n)[::-1]:
        position=0
        for j in range(1,i):
            if data[j]<data[j-1]:
                position=j
                data[j],data[j-1]=data[j-1],data[j]
        i=position
    Print(data)
'''冒泡排序优化方法3---双向交换'''
def bubbleSortOpt3(data,n):
    for i in range(n):
        change=0
        for j in range(1,n/2):
            if data[j]<data[j-1]:
                data[j],data[j-1]=data[j-1],data[j]
        for k in range(n/2,n)[::-1]:
            if data[k]<data[k-1]:
                data[k],data[k-1]=data[k-1],data[k]
    Print(data)
'''快速排序'''
def splitData(data,low,high):   #分割函数，将数据以keyValue为界分为两部分
    keyValue=data[low]
    while(low<high):
        #大于分界值部分
        while(low<high and data[high]>=keyValue):
            high-=1
        data[low],data[high]=data[high],data[low]
        #小于分解值部分
        while(low<high and data[low]<=keyValue):
            low+=1
        data[low],data[high]=data[high],data[low]
    return data,low
def quickSort(data,low,high):
    if(low<high):
        data,pos=splitData(data,low,high)  #分割
        data=quickSort(data,pos+1,high)    #对大于分界值部分递归调用快速排序
        data=quickSort(data,0,pos-1)       #对小于分界值部分递归调用快速排序
    return data
'''快速排序优化'''
def quickSortOpt(data,low,high,k):
    if (high-low)>k:
        data,pos=splitData(data,low,high)
        data=quickSortOpt(data,pos+1,high,k)
        data=quickSortOpt(data,0,pos-1,k)
    return data
def quickSortOpt1(data,low,high,k):
    data=quickSortOpt(data,low,high,k)     #获得基本有序序列
    for i in range(len(data)):             #插入排序
        temp=data[i]
        j=i-1
        while(j>0 and data[j]>temp):
            data[j+1]=data[j]
            j=j-1
        data[j+1]=temp
    Print(data)
'''归并排序'''
def Merge(data,rf,i,m,n):
    j=m+1;k=i                 #两个待归并数组的初始下标
    '''将两待归并数组中的较小元素依次赋给rf'''
    while(i<=m and j<=n):     #两个待归并数组长度
        if data[i]<=data[j]:
            rf[k]=int(data[i])
            i+=1;k+=1
        else:
            rf[k] =int(data[j])
            j+=1;k+=1
    '''将两归并数组中的剩余元素赋给rf'''
    while(i<=m):
        rf[k] = int(data[i])
        i+=1;k+=1
    while(j<=n):
        rf[k] = int(data[j])
        j+=1;k+=1
def MergeSort(data,n):
    rf=zeros(n)
    len=1
    while(len<n):
        i=0
        s=len
        len=2*s
        '''对两两成对的数组归并'''
        while(i+len<n):
            Merge(data,rf,i,i+s-1,i+len-1)
            i=i+len
        '''对单出的数组归并'''
        if(i+s<=n):
            Merge(data,rf,i,i+s-1,n-1)
        data,rf=rf,data
    print '排序结果为：'
    Print(data)
'''基数排序'''
def maxRadix(data,n):        #获取数据最大位数
    d=0
    maxValue=max(data)
    while(maxValue>0):
        maxValue=maxValue/10
        d+=1
    return d
def RadixSort(data,n):
    d=maxRadix(data,n)
    RadData=zeros(n)
    rad=1                          #位标志，个位为1，十位为10。。。
    i=1                            #数据位数标志
    while(i<=d):                   #循环d次
        count=zeros(10)            #每个桶中数据个数,每次循环开始清零
        for j in range(n):
            k=(data[j]/rad)%10
            count[k]+=1            #统计个数
        for m in range(1,10):
            count[m]+=count[m-1]   #计算相应位数据个数
        for l in range(n)[::-1]:
            kk=(data[l]/rad)%10
            RadData[count[kk]-1]=data[l]
            count[kk]-=1
        for ii in range(n):
            data[ii]=int(RadData[ii])
        rad*=10
        i+=1
    Print(data)



